\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 4}}
\end{center}

\noindent{\textbf{Exercise 4.1}}\\\\
\begin{tabular}{ll}
  a) formula & f) meta language \\
  b) ground term, term & g) formula \\
  c) meta language& h) formula \\
  d) meta language & i) formula \\
  e) term & j) meta language\\
\end{tabular}

\vspace{1cm}
\noindent{\textbf{Exercise 4.2}}\\\\
(a)\\\\
First of all, let's specify a first-order signature for the set of formulae:\\
S = \{V, C, F, R\}\\
V = \{x,y,z\}, C = $\emptyset$, F = $\emptyset$, R = \{P\} where arity(P)=2.\\\\
The universe is given and it is D = \{d1,...,d4\}. So, in order to specify the interpretation, we have to define a function $^{.I}$. The function assigns meaning to constants, function and relation symbols, but since we only have relation symbols:\\
P$^{I}$ = \{(d1,d2),(d2,d3),(d3,d4), (d1,d3), (d2,d4), (d1,d4)\}.\\
We also need a variable assignment, which in this case it could be set in this way:\\
$\alpha$ = \{x$\rightarrow$d1, y$\rightarrow$d2, z$\rightarrow$d3\}.\\\\
Now we can use this Interpretation to prove every formula and therefore that I $\vDash$ KB. Let's start with the first one:\\\\
1) $\forall$x $\neg$P(x,x)\\
I, $\alpha$ $\vDash$ $\forall$x $\neg$P(x,x) iff \\
I, $\alpha$[x:=d1] $\vDash$ $\neg$P(x,x) and \\
I, $\alpha$[x:=d2] $\vDash$ $\neg$P(x,x) and \\
I, $\alpha$[x:=d3] $\vDash$ $\neg$P(x,x) and \\
I, $\alpha$[x:=d4] $\vDash$ $\neg$P(x,x). \\
If we consider the first one in detail, the interpretation satisfies the formula iff\\
I, $\alpha$[x:=d1] $\nvDash$ P(x,x) and therefore iff (d1,d1)$\notin$ P$^{I}$, which is true.\\
The same procedure can be applied to the other three variable assignment  $\alpha$[x := d]. Therefore I satisfies 1).\\\\
2)  $\forall$x$\forall$y$\forall$z ((P(x,y) $\wedge$ P(y,z)) $\rightarrow$ P(x,z)\\
The interpretation satisfies the formula iff\\
I, $\alpha$ [x:=d$_{i}$, y:=d$_{j}$, z:=d$_{z}$] ((P(x,y) $\wedge$ P(y,z)) $\rightarrow$ P(x,z). We have to consider all the possible combinations of x, y, z. In order to skip the prove of every case we can reason in this way: the first part of the formula is (P(x,y) $\wedge$ P(y,z). When a combination of x,y,z make this formula false, the whole implication is true. On the other hand, if (P(x,y) $\wedge$ P(y,z) is true, we can easily verify that P(x,z) is also true, because P is closed with respect to transitivity. Therefore  I satisfies 2)\\\\
3) $\forall$x$\forall$y (P(x,y) $\vee$ x=y $\vee$ P(y,x))\\
Again, the interpretation satisfies the formula iff\\
I, $\alpha$ [x:=d$_{i}$, y:=d$_{j}$] (P(x,y) $\vee$ x=y $\vee$ P(y,x)). When we consider all the possible combinations of x and y:\\
we can easily see that when x=y, the interpretation satisfies:\\
I, $\alpha$ [x:=d$_{i}$, y:=d$_{i}$] x=y and therefore all the disjunction is also satisfied.\\
In all the other cases:
I, $\alpha$ [x:=d$_{i}$, y:=d$_{i}$] P(x,y) $\vee$ P(y,x) (at least one of them is always true).
\\\\
Even if a variable assignment $\alpha$ was specified, this was not necessary because every formula has only bounded variables.\\\\
(b)\\\\
There are also models of KB with an infinite domain D. For instance, if D represented the elements of the set of natural numbers $\mathbb{N}$, we could define the interpretation in this way:\\
P$^{I}$ = \{(d$_{i}$,d$_{i+1}$),(d$_{i}$,d$_{i+2}$), (d$_{i}$,d$_{i+3}$), ...\} for all i $\in$  $\mathbb{N}$.\\






\vspace{1cm}
\noindent{\textbf{Exercise 4.3}}\\\\

\includegraphics[width=0.5\textwidth]{exercise4_3.png}

\end{document}

